package lyl.sort;

public class MergeSort {

    public void mergeSort(int[] arr){
        int start = 0;
        int end = arr.length - 1;
        int[] temp = new int[arr.length];
        mergeSortImpl(arr,start,end,temp);

    }

    private void mergeSortImpl(int[] arr, int start , int end ,int[] temp){
        if(start>=end){
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSortImpl(arr,start,mid,temp);//拆左边
        mergeSortImpl(arr,mid + 1,end,temp);//拆右边
        merge(arr,start,mid,end,temp); //456 123    start 0 mid 2 end 5
    }

    private void merge(int[] arr,int start, int mid,int end,int[] temp){
        int left = start; //左边开始位置
        int right = mid + 1; //右边开始位置
        int index = start;
        while(left<=mid && right<=end){
            if(arr[left]>arr[right]){
                temp[index++] = arr[right++];
            }else {
                temp[index++] = arr[left++];
            }
        }
        //将另一边的放入临时数组
        while(left<=mid){
            temp[index++] = arr[left++];
        }
        while(right<=end){
            temp[index++] = arr[right++];
        }
        for(index = start ; index <=end;index++){
            arr[index] = temp[index];
        }
    }


}
